package br.ufrn.ciencomp.grafos;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

import br.ufrn.ciencomp.grafos.Grafo.Tipo;

public class BellmanFord {
	private static int[] dist, pre;

	public static boolean bellmanFord(Grafo g, int origem){
		dist = new int[g.getN()];
		pre = new int[g.getN()];
		
		for(int i = 0; i < g.getN(); i++) {
			if(i == origem)
				dist[i] = 0;
			else
				dist[i] = 9999;
		}
		
		for(int i = 0; i < g.getN(); i++) {
			for(Aresta a : g.getArestas()) {
				if(dist[a.getOrigem()] + a.getPeso() < dist[a.getDestino()]) {
					dist[a.getDestino()] = dist[a.getOrigem()] + a.getPeso();
					pre[a.getDestino()] = a.getOrigem();
				}
			}
		}
		
		for(Aresta a : g.getArestas()) {
			if(dist[a.getOrigem()] + a.getPeso() < dist[a.getDestino()]) {
				return true;
			}
		}
		
		return false;
    }
	
	public static void caminho(int destino) {
		if(dist[destino] != 9999) {
			int n = destino;
			
			Stack<Integer> pilha = new Stack<Integer>();
			while(n != 0) {
				pilha.push(n);
				n = pre[n];
			}
			
			while(!pilha.isEmpty()) {
				System.out.print(pilha.pop() + " ");
			}
			
			System.out.println(dist[destino]);
		} else {
			System.out.println("No path");
		}
	}
	
	public static void main(String args[]) {
		try {
			Scanner scanner = new Scanner(new File("streams/bellmanford3.in"));
			
			Grafo g = new Grafo(scanner.nextInt(), Tipo.LISTA);
			
			while(scanner.hasNext()) {
				String instrucao = scanner.next();
				if(instrucao.startsWith("edge")) {
					g.addAresta(
							scanner.nextInt(), 
							scanner.nextInt(), 
							scanner.nextInt());
					System.out.println("-");
				} else if(instrucao.equals("hasNegativeCicle")) {
					if(bellmanFord(g, 1)) {
						System.out.println("true");
						break;
					} else {
						System.out.println("false");
					}
				} else if(instrucao.equals("shortest")) {
					bellmanFord(g, scanner.nextInt());
					caminho(scanner.nextInt());
				}
			}
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
}